class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        mod = 10 ** 9 + 7

        power, rep = [], 1
        while n > 0:
            if n % 2 == 1:
                power.append(rep)
            n //= 2
            rep *= 2
        
        ans = []
        for left, right in queries:
            cur = 1
            for i in range(left, right + 1):
                cur = cur * power[i] % mod
            ans.append(cur)
        return ans


#方法二预处理
class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        mod = 10 ** 9 + 7

        power, rep = [], 1
        while n > 0:
            if n % 2 == 1:
                power.append(rep)
            n //= 2
            rep *= 2
        
        m = len(power)
        results = [[0] * m for _ in range(m)]
        for i in range(m):
            cur = 1
            for j in range(i,m):
                cur = cur * power[j] % mod
                results[i][j] = cur

        ans = []
        for left, right in queries:
            ans.append(results[left][right])
        return ans